package com.ztl.leetcode.SwordFingerOffer;

/**
 * @author @ztl
 * @ClassName:MinPathSum
 * @Package:com.ztl.leetcode.SwordFingerOffer
 * @date 2023年06月02日 21:36
 * @description: 给定一个包含非负整数的 m * n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * @version: 1.0
 */
public class MinPathSum {

    //遍历一次二维数组，时间复杂度O(mn)，原地修改数组，空间复杂度O(1)
    public int minPathSum(int[][] grid) {
        //思路：由于题目要求只能向下或者向右移动，即当前格子只能通过上格子或者左格子到达
        //由上分析出：到达当前格子最小路径=上格子与左格子之间最小的路径数+当前格子数字
        //因此只需要从左上到右下遍历一遍二维数组，按照上述规则计算每个格子最小路径数即可

        //外层循环遍历行
        for(int i = 0; i < grid.length; i++) {
            //内层循环遍历列
            for(int j = 0; j < grid[0].length; j++) {
                //第一个格子数字可以确定，需要跳过
                if(i == 0 && j == 0) continue;

                    //对于第一行的格子，只可能从左格子到达，即grid[i][j-1]
                else if(i == 0) {
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                }
                //对于第一列的格子，只可能从上格子到达，即grid[i-1][j]
                else if(j == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                }
                //其它格子则比较上格子与左格子之间最小值，然后与自身数字相加
                else {
                    grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
        }

        //经过一轮遍历计算，计算出从左上到右下最小路径
        return grid[grid.length - 1][grid[0].length - 1];
    }
}
